//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include "common/exception.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {}

/*
* 思路：Evict函数需要遍历所有的LRUKNode，找到最大的backward k-distance，然后返回。
* 当有多个backward k-distance相同时，返回最早的那个，既history_.back()最小的那个。
* 如果没有找到backward k-distance，返回false。
* 函数结果是返回一个frame_id，这个frame_id是需要被evict的，而replacer的cur_size减一。
*/
auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool { 
    if(this->curr_size_ == 0){
        return false;
    }
    size_t max_backward_k_distance = 0;
    frame_id_t max_backward_k_distance_frame_id = INVALID_PAGE_ID;
    for(auto it = this->node_store_.begin(); it != this->node_store_.end(); it++){
        if(it->second.IsEvictable()){
            if(it->second.GetBackwardKDistance(this->current_timestamp_) > max_backward_k_distance){
                max_backward_k_distance = it->second.GetBackwardKDistance(this->current_timestamp_);
                max_backward_k_distance_frame_id = it->first;
            }else if(it->second.GetBackwardKDistance(this->current_timestamp_) == max_backward_k_distance){
                if(it->second.GetHistory().back() < this->node_store_[max_backward_k_distance_frame_id].GetHistory().back()){
                    max_backward_k_distance_frame_id = it->first;
                }
            }
        }
    }
    *frame_id = max_backward_k_distance_frame_id;
    if(max_backward_k_distance_frame_id == INVALID_PAGE_ID){
        return false;
    }
    Remove(max_backward_k_distance_frame_id);
    return true;
}

/*
* RecordAccess函数需要更新被访问的frame_id的时间戳。如果没有被访问过，需要创建一个新的LRUKNode。
* 如果已经被访问过，需要更新时间戳。
* 如果frame_id超过了replacer_size_，需要抛出异常。
*/

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
    if((uint64_t)frame_id>=this->replacer_size_){
        BUSTUB_ASSERT(false, "frame_id超过了replacer_size_");
    }
    if(this->node_store_.find(frame_id) == this->node_store_.end()){
        this->node_store_[frame_id] = LRUKNode(frame_id, this->k_);
    }
    this->node_store_[frame_id].RecordAccess(this->current_timestamp_);
    this->current_timestamp_++;
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
    if((uint64_t)frame_id>=this->replacer_size_){
        BUSTUB_ASSERT(false, "frame_id超过了replacer_size_");
    }
    if(this->node_store_[frame_id].IsEvictable() && !set_evictable){
        this->curr_size_--;
    }
    if(!this->node_store_[frame_id].IsEvictable() && set_evictable){
        this->curr_size_++;
    }
    this->node_store_[frame_id].SetEvictable(set_evictable);
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
    if((uint64_t)frame_id>=this->replacer_size_){
        BUSTUB_ASSERT(false, "frame_id超过了replacer_size_");
    }

    if(this->node_store_[frame_id].IsEvictable()){
        this->node_store_.erase(frame_id);
        this->curr_size_--;
    }else{
        BUSTUB_ASSERT(false, "frame_id不可被删除");
    }

}

auto LRUKReplacer::Size() -> size_t { return this->curr_size_; }

}  // namespace bustub
